/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-02-07
 * Time:12:17
 */
/**
 *你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。
 *
 * 为了使收益最大化，矿工需要按以下规则来开采黄金：
 *
 * 每当矿工进入一个单元，就会收集该单元格中的所有黄金。
 * 矿工每次可以从当前位置向上下左右四个方向走。
 * 每个单元格只能被开采（进入）一次。
 * 不得开采（进入）黄金数目为 0 的单元格。
 * 矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止
  */
//回溯算法
public class test {
    //维护最大值
    int ans = 0;
    //复制一个二维数组
    int grid[][];

    public int getMaximumGold(int[][] grid) {
        this.grid = grid;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] > 0) {
                    //枚举每个黄金点作为起点
                    getGold(i, j, 0);
                }
            }
        }
        return ans;
    }

    public void getGold(int i, int j, int gold) {
        //不符合条件直接return
        if (i == -1 || j == -1 || i == grid.length || j == grid[0].length || grid[i][j] == 0) {
            return;
        }
        //记录该位置的数值
        int g = grid[i][j];
        gold += g;
        //把该位置置为空是因为防止重复进入
        grid[i][j] = 0;
        ans = Math.max(ans, gold);
        getGold(i + 1, j, gold);
        getGold(i - 1, j, gold);
        getGold(i, j + 1, gold);
        getGold(i, j - 1, gold);
        //把该位置的值复原 进行下一次遍历
        grid[i][j] = g;
    }
}
